package leetcode100;

// TODO 中序遍历 [经典 | 困难] 【-】 验证二叉搜索树
// TODO https://leetcode.cn/problems/validate-binary-search-tree/solution/zhong-xu-bian-li-qing-song-na-xia-bi-xu-miao-dong-/

public class lc100_0098 {

    long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        return dfs(root);
    }

    public boolean dfs(TreeNode node) {
        if (node == null) {
            return true;
        }

        // 访问左子树
        if (!isValidBST(node.left)) {
            return false;
        }
        // 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足 BST，返回 false；否则继续遍历。
        if (node.val <= pre) {
            return false;
        }
        pre = node.val;
        // 访问右子树
        if (!isValidBST(node.right)) {
            return false;
        }

        return true;
    }

}
